칸토어의 정리

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 정의
3. 증명
- 3.1. 증명의 또 다른 표현
4. 역사
5. 관련 역설
6. 일반화
7. 정리 기반의 결과
- 7.1. 칸토어의 역설
8. 구체적인 예: 가산 무한 집합의 경우
참조

1. 개요

칸토어의 정리는 집합 X의 멱집합 2^X의 크기가 항상 원래 집합 X의 크기보다 크다는 정리이다. 즉, 임의의 기수 κ에 대해 2^κ > κ가 성립한다. 이 정리는 임의의 집합 A에 대해 A의 모든 부분 집합의 집합(A의 멱집합)은 A 자신보다 진정으로 큰 농도를 갖는다는 것을 의미한다. 칸토어의 정리는 대각선 논법을 사용하여 증명할 수 있으며, 가산 집합의 경우 표를 구성하여 논증을 설명할 수 있다. 이 정리는 집합론의 역설과 관련 있으며, "모든 집합의 집합"을 가정하면 모순이 발생한다. 칸토어의 정리는 무한 집합의 크기에 대한 중요한 결과를 제시하며, 연속체 가설과도 관련이 있다.

더 읽어볼만한 페이지

1891년 과학 - 택시미터
택시미터는 이동 거리와 시간 측정으로 택시 요금을 계산하는 장치로, 기술 발전을 거쳐 기계식에서 전자식으로, GPS 등과 융합되어 스마트해졌으며, 요금 체계 공정성 확보에 중요한 역할을 한다.
1891년 과학 - 피셔 투영식
피셔 투영식은 유기화학에서 분자의 3차원 구조를 2차원 평면에 나타내는 방법으로, 특히 여러 개의 비대칭 탄소를 가진 분자를 표현하고 카이랄성 분석을 용이하게 하며, 특정 규칙에 따라 분자를 정렬하여 투영하는 방식을 사용하고, 약물 개발 분야에서 카이랄성 결정에 중요한 역할을 한다.
게오르크 칸토어 - 칸토어 역설
칸토어 역설은 가장 큰 기수가 존재한다는 가정의 모순을 통해 기수들의 모임이 집합이 아닌 고유 모임임을 보이는 역설이다.
게오르크 칸토어 - 대각선 논법
대각선 논법은 자연수 집합과 실수 구간 사이에 전단사 함수가 존재하지 않음을 증명하는 방법으로, 실수 집합이 비가산 집합임을 보이는 것과 동치이며, 칸토어 정리를 증명하고 정지 문제의 결정 불가능성을 증명하는 데에도 사용되는 등 집합론과 수학 전반에 걸쳐 활용된다.
기수 - 초한수
초한수는 게오르크 칸토어가 도입한 무한 개념을 확장한 수로, 집합의 크기를 나타내는 기수와 정렬된 집합 내의 위치를 나타내는 서수로 나뉘며, 무한에도 여러 종류가 있음을 밝혀 현대 수학의 기초를 다졌다.
기수 - 연속체 가설
연속체 가설은 가산 무한 집합의 크기와 실수 집합의 크기 사이에 다른 기수가 존재하지 않는다는 명제들의 동치이며, 체르멜로-프렠켈 집합론으로부터 독립임이 증명되었다.

칸토어의 정리
일반 정보
이름	칸토어의 정리
분야	집합론
발견자	게오르크 칸토어
발견 시기	1891년
중요성	집합의 크기에 대한 중요한 결과 제공 무한에도 여러 종류가 있음을 보여줌 러셀의 역설과 같은 집합론의 역설을 해결하는 데 기여
내용
정리	모든 집합 X에 대해, X의 멱집합 P(X)의 크기는 X의 크기보다 항상 크다.
수식 표현	\|X\| < \|P(X)\|
설명	\|X\|는 집합 X의 크기(cardinality)를 나타낸다. P(X)는 집합 X의 멱집합(power set)을 나타낸다. 즉, 집합 X의 모든 부분집합을 원소로 갖는 집합이다.
예시	집합 X = {a, b}가 있을 때, P(X) = { {}, {a}, {b}, {a, b} }이다. 따라서 \|X\| = 2이고, \|P(X)\| = 4이다. 칸토어의 정리에 따라 \|X\| < \|P(X)\|가 성립한다.
증명 방법	귀류법을 사용하여 증명한다. 만약 \|X\| ≥ \|P(X)\|라면, X에서 P(X)로의 전사 함수 f가 존재해야 한다. 집합 Y = { x ∈ X \| x ∉ f(x) }를 정의한다. Y는 X의 부분집합이므로, Y ∈ P(X)이다. 따라서 어떤 y ∈ X에 대해 f(y) = Y가 성립해야 한다. 만약 y ∈ Y라면, y ∉ f(y) = Y이므로 모순이다. 만약 y ∉ Y라면, y ∈ f(y) = Y이므로 모순이다. 따라서 X에서 P(X)로의 전사 함수 f는 존재하지 않는다. 즉, \|X\| < \|P(X)\|이다.
결과	칸토어의 정리는 무한에도 여러 종류가 있음을 보여준다. 자연수 집합 N의 멱집합 P(N)은 N보다 더 큰 무한 집합이다. P(N)의 멱집합 P(P(N))은 P(N)보다 더 큰 무한 집합이다. 이 과정을 무한히 반복하면, 무한히 많은 종류의 무한 집합을 얻을 수 있다.
관련 개념
관련 개념	집합론 멱집합 기수 무한 대각선 논법 러셀의 역설
참고 문헌
참고 문헌	Cantor, Georg (1891). "Ueber eine elementare Frage der Mannigfaltigkeitslehre". Jahresbericht der Deutschen Mathematiker-Vereinigung. 1: 75–78. Jech, Thomas (2003). Set Theory. Springer Monographs in Mathematics. Berlin: Springer-Verlag. ISBN 3-540-44085-2.

2. 정의

집합 $X$ 의 멱집합 $2^X$ 는 $X$ 의 모든 부분 집합의 집합이다.

'''칸토어의 정리'''에 따르면, 멱집합 $2^X$ 의 크기는 항상 원래의 집합 $X$ 의 크기보다 크다. 즉, 다음이 성립한다.

: $|2^X|>|X|$

즉, 임의의 기수 $\kappa$ 에 대하여, 다음이 성립한다.

: $2^\kappa>\kappa$

임의의 집합 A에 대해, A의 모든 부분 집합의 집합(A의 멱집합)은 A 자신보다 진정으로 큰 농도를 갖는다.

3. 증명

칸토어의 정리는 대각선 논법을 사용하여 증명할 수 있다.

우선, 집합 $X$ 가 공집합( $X=\varnothing$ )인 경우, $|\varnothing|=0<1=|\{\varnothing\}|=|2^\varnothing|$ 이므로 정리가 성립한다.

$X$ 가 공집합이 아닌 경우( $X\ne\varnothing$ ), 단사 함수 $X\to2^X$ ( $x\mapsto\{x\}$ )가 존재하므로 $|X|\le|2^X|$ 이다.

만약 $|X|=|2^X|$ 라고 가정하면, 전단사 함수 $f\colon X\to 2^X$ 가 존재한다. 이 경우, $f(a)=\{x\in X\colon x\not\in f(x)\}\in2^X\qquad(a\in X)$ 를 생각할 수 있는데, $f(a)$ 의 정의에 따라 $a\in f(a)\iff a\not\in f(a)$ 이며, 이는 모순이다. 즉, $|X|\ne|2^X|$ 이므로, $|X|<|2^X|$ 이다.

$A$ 가 가산 무한 집합인 경우, 일반성을 잃지 않고 $A = \mathbb{N} = \{1,2,3,\ldots\}$ (자연수의 집합)으로 둘 수 있다. $\mathbb{N}$ 과 그 멱집합 $\mathcal{P}(\mathbb{N})$ 이 대등하다고 가정하고, $\mathbb{N}$ 의 각 원소를 $\mathcal{P}(\mathbb{N})$ 의 원소와 짝짓는 시도를 하면 다음과 같다.

: $\mathbb{N}\begin{Bmatrix} 1 & \longleftrightarrow & \{4, 5\}\\ 2 & \longleftrightarrow & \{1, 2, 3\} \\ 3 & \longleftrightarrow & \{4, 5, 6\} \\ 4 & \longleftrightarrow & \{1, 3, 5\} \\ \vdots & \vdots & \vdots \end{Bmatrix}\mathcal{P}(\mathbb{N}).$

여기서 자신과 같은 수를 포함하는 부분 집합과 짝을 이루는 자연수를 '이기적', 그렇지 않은 자연수를 '비이기적'이라고 정의한다. 그리고 $B$ 를 모든 비이기적 자연수의 집합이라고 하면, $B$ 는 $\mathcal{P}(\mathbb{N})$ 의 원소이지만 어떤 자연수와도 짝을 이룰 수 없어 모순이 발생한다. 따라서 $\mathbb{N}$ 과 $\mathcal{P}(\mathbb{N})$ 의 기수는 같을 수 없다.

또한, $\mathcal{P}(\mathbb{N})$ 은 모든 단일 집합을 포함하고, 이러한 단일 집합은 $\mathcal{P}(\mathbb{N})$ 내에서 $\mathbb{N}$ 의 "복사본"을 형성하기 때문에 $\mathcal{P}(\mathbb{N})$ 의 기수가 $\mathbb{N}$ 의 기수보다 작을 수 없다. 그러므로 $\mathcal{P}(\mathbb{N})$ 의 기수가 $\mathbb{N}$ 의 기수보다 엄격하게 크다는 결론을 내릴 수 있다.

가산(또는 유한) 집합의 경우, 증명의 논증은 다음과 같은 표를 구성하여 설명할 수 있다.^[3]

가산 집합의 경우 칸토어 대각선 논법
	$f(x_1)$	$f(x_2)$	$f(x_3)$	$f(x_4)$	$\cdots$
$x_1$	T	T	F	T	$\cdots$
$x_2$	T	F	F	F	$\cdots$
$x_3$	F	F	T	T	$\cdots$
$x_4$	F	T	T	T	$\cdots$
$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\ddots$

여기서 주 대각선 $D$ 는 각 $x\in A$ 에 대해 $x\in f(x)$ 인지 여부를 나타낸다. $B$ 는 주 대각선의 항목을 논리 부정한(참/거짓을 바꾼) 집합으로, 어떤 열과도 일치하지 않아 $B$ 를 나타내는 열은 존재하지 않는다.

3. 1. 증명의 또 다른 표현

두 집합의 크기(농도)가 같다는 것은 그들 사이에 전단사 함수(일대일 대응)가 존재한다는 것을 의미한다. 칸토어의 정리를 증명하기 위해서는, 임의의 집합 *A*에 대해 *A*에서 *A*의 멱집합으로의 어떤 함수 *f*도 전사 함수가 될 수 없음을 보이는 것으로 충분하다.

이를 위해 *f*에 의한 *A*의 상(image)의 원소가 아닌 *A*의 부분집합 *B*를 다음과 같이 구성한다.^[1]^[2]

:

B=\{x\in A \mid x\not\in f(x)\}.

이는 모든

x\in A

에 대해,

x\in B

는

x\notin f(x)

일 경우에만 해당함을 의미한다.

B*는 *f*에 의해 자신을 포함하지 않는 *A*의 원소로 구성되었기 때문에, 모든 *x*에 대해 집합 *B*와 *f(x)*는 같을 수 없다. 즉:

만약 $x\in f(x)$ 이면, $x\in f(x)$ 이고 정의에 의해 $x\notin B$ 이므로, $f(x)$ 는 *B*와 같을 수 없다.
만약 $x\notin f(x)$ 이면, $x\notin f(x)$ 이고 *B*의 정의에 의해 $x\in B$ 이므로, $f(x)$ 는 *B*와 같을 수 없다.

따라서,

f(\xi)=B

를 만족하는

\xi \in A

는 존재하지 않는다. 즉, *B*는 *f*의 상에 있지 않으며, *f*는 *A*의 멱집합의 모든 원소에 매핑되지 않는다. 즉, *f*는 전사가 아니다.^[3]

이러한 집합 *B*는 *f*의 칸토어 대각선 집합이라고 불린다.

B*가 공집합이든 아니든 항상 *A*의 멱집합에 포함된다는 점을 이용하여 증명을 이해할 수도 있다. *f*가 전사 함수가 되려면, *A*의 어떤 원소는 *B*에 매핑되어야 한다. 그러나 *B*의 어떤 원소도 *B*에 매핑될 수 없다. 왜냐하면 이는 *B*의 구성 조건에 모순되기 때문이다. 따라서 *B*에 매핑되는 원소는 *B*의 원소가 아니어야 한다. 그런데 이는 *B*의 구성 조건을 만족시키므로 또 다른 모순이다. 따라서 *A*의 어떤 원소가 *B*에 매핑된다는 가정은 틀렸고, *f*는 전사 함수가 될 수 없다.

표현식 "

x\in f(x)

"에서

x

가 두 번 나타나기 때문에, 이 논법은 대각선 논법이다.

4. 역사

게오르크 칸토어는 1891년에 발표한 논문 "Über eine elementare Frage der Mannigfaltigkeitslehre"에서 이 정리를 제시하였다.^[6] 이 논문에서 대각선 논법이 실수의 비가산성을 증명하기 위해 처음 등장했으며, 칸토어는 이전에 다른 방법으로 실수의 비가산성을 증명한 적이 있었다. 해당 논문에서 칸토어는 집합의 부분 집합 대신 집합의 지시 함수를 사용하여 논증을 제시했다.^[7]

버트런드 러셀은 ''수학 원리''(1903)에서 칸토어와 매우 유사한 증명을 제시하면서, 명제 함수가 객체보다 더 많다는 것을 보였다. 러셀은 이 증명의 아이디어를 칸토어에게서 얻었다고 언급했다.

에른스트 체르멜로는 1908년에 출판된 논문("Untersuchungen über die Grundlagen der Mengenlehre I")에서 칸토어의 정리와 동일한 형태의 정리를 제시했으며, 이 논문은 현대 집합론의 기초가 되었다. 체르멜로는 이 정리를 "칸토어의 정리"라고 불렀다.

5. 관련 역설

칸토어의 역설은 모든 집합을 포함하는 집합, 즉 전체 집합 $V$ 가 존재한다는 가정과 함께 칸토어의 정리에 의해 발생하는 모순에 붙여진 이름이다. 칸토어의 정리에 따르면 모든 집합 $X$ 에 대해 $|\mathcal{P}(X)| > |X|$ 이다. 반면, $\mathcal{P}(V)$ 의 모든 원소는 집합이므로 $V$ 에 포함되며, 따라서 $|\mathcal{P}(V)| \leq |V|$ 이다.^[1]

또 다른 역설은 칸토어의 정리 증명에서 함수 ''f''를 항등 함수로 인스턴스화하여 파생될 수 있다. 이것은 칸토어의 대각선 집합을 주어진 집합 ''A''의 때때로 ''러셀 집합''이라고 불리는 것으로 바꾼다.^[1]

: $R_A=\left\{\,x\in A : x\not\in x\,\right\}.$

칸토어의 정리 증명은 모든 집합의 집합 ''U''가 존재한다고 가정하고, 러셀 집합 ''R''_''U''을 고려하면 다음의 모순에 이르게 된다는 것을 보여주기 위해 간단히 적용된다.

: $R_U \in R_U \iff R_U \notin R_U.$

이 주장은 러셀의 역설로 알려져 있다.^[1] 여기서 얻은 모순으로부터 ''R''_''U''∈''U''라는 가설을 거부해야 하며, 따라서 모든 집합을 포함하는 집합의 존재를 부정해야 한다고 결론지을 수 있다.

소박 집합론에서 칸토어의 정리는 역설을 이끌어낸다. "모든 집합의 집합" $X$ 를 생각한다. 칸토어의 정리에 의해, $X$ 의 멱집합 $\mathfrak P(X)$ 는 $X$ 보다 진정으로 큰 농도를 가진다. 그러나 $X$ 는 모든 집합을 그 부분 집합으로 가지므로, $X$ 는 $\mathfrak P(X)$ 보다 큰 농도를 가질 것이다. 이것은 모순이다.

역사적으로 이 결과는 공리적 집합론의 성립을 촉진했다. 현재의 집합론에서는 "모든 집합의 집합"은 공리로부터 구성 불가능하기 때문에 역설이 회피되고 있으며, $X$ 와 같은 집합의 모임은 진 클래스라고 불린다.

6. 일반화

로베어의 고정점 정리는 칸토어의 정리를 범주의 유한 곱으로 일반화한다.^[8] 어떤 범주에서 대상 $Y$ 가 고정점을 갖지 않는 자기 사상, 즉 $\alpha \circ y = y$ 를 만족하는 사상 $y:1 \to Y$ 가 존재하지 않는 $\alpha : Y \to Y$ 가 있다고 가정한다. 그렇다면, 사상 $f: T \times T \to Y$ 가 모든 사상 $T \to Y$ 를 매개변수화 할 수 있는 대상 $T$ 는 존재하지 않는다. 다시 말해, 모든 대상 $T$ 와 모든 사상 $f : T \times T \to Y$ 에 대해, $T \to Y$ 를 $f(-,x) : T \to Y$ 형태의 맵으로 쓰려고 하면 적어도 하나의 맵 $T \to Y$ 는 제외해야 한다.

7. 정리 기반의 결과

칸토어의 정리는 "어떤 무한 집합을 생각하더라도, 그것보다 더 큰 농도를 가진 무한 집합이 존재한다"는 것을 보여준다. 특히, 가산 무한 집합의 멱집합은 비가산 무한이다.^[1]

원래 집합의 농도와 멱집합의 농도 사이에 다른 농도가 존재하는지는 연속체 가설과 관련이 있다.

7. 1. 칸토어의 역설

칸토어의 정리는 소박 집합론에서 역설을 이끌어낸다.^[1]

"모든 집합의 집합"을 생각하면, 칸토어의 정리에 따라 모순이 발생한다. 모든 집합을 포함하는 집합, 즉 전체 집합

V

가 존재한다고 가정하고 칸토어의 정리를 적용하면, 모든 집합

X

에 대해

|\mathcal{P}(X)| > |X|

이다. 반면,

\mathcal{P}(V)

의 모든 원소는 집합이므로

V

에 포함되며, 따라서

|\mathcal{P}(V)| \leq |V|

라는 결론이 나온다.

이 결과는 형식적/공리적 집합론의 성립을 촉진했다. 현재의 집합론에서는 "모든 집합의 집합"은 공리로부터 구성 불가능하므로 이러한 역설은 회피된다.

8. 구체적인 예: 가산 무한 집합의 경우

자연수 집합 $\mathbb{N}$ 과 그 멱집합 $\mathcal{P}(\mathbb{N})$ 의 관계를 통해 칸토어의 정리를 구체적으로 설명할 수 있다. $\mathbb{N}$ 과 $\mathcal{P}(\mathbb{N})$ 사이에 전단사 함수가 존재한다고 가정하고, 원소를 짝짓는 시도를 통해 모순을 보인다.

: $\mathbb{N}\begin{Bmatrix} 1 & \longleftrightarrow & \{4, 5\}\\ 2 & \longleftrightarrow & \{1, 2, 3\} \\ 3 & \longleftrightarrow & \{4, 5, 6\} \\ 4 & \longleftrightarrow & \{1, 3, 5\} \\ \vdots & \vdots & \vdots \end{Bmatrix}\mathcal{P}(\mathbb{N}).$

위와 같이 짝짓는다고 할때, 일부 자연수는 자신을 원소로 포함하는 부분 집합과 짝을 이룬다. 예를 들어, 숫자 2는 {1, 2, 3}과 짝을 이루는데, 2는 이 집합의 원소이다. 이러한 숫자를 "이기적"이라고 부른다. 반면, 자신을 포함하지 않는 부분 집합과 짝을 이루는 자연수도 있는데, 예를 들어 숫자 1은 {4, 5}와 짝을 이루는데, 1은 이 집합의 원소가 아니다. 이러한 숫자를 "비이기적"이라고 부른다.

이 개념을 사용하여, "모든 비이기적 자연수의 집합" $B$ 를 정의한다. $B$ 는 $\mathcal{P}(\mathbb{N})$ 의 원소이므로, 만약 $\mathbb{N}$ 과 $\mathcal{P}(\mathbb{N})$ 사이에 전단사 함수가 존재한다면, $B$ 는 어떤 자연수 $b$ 와 짝을 이루어야 한다. 그러나 이는 모순을 일으킨다.

$b$ 가 $B$ 의 원소라면, $b$ 는 이기적이 되어 $B$ 의 정의에 모순된다.
$b$ 가 $B$ 의 원소가 아니라면, $b$ 는 비이기적이 되어 $B$ 의 원소가 되어야 한다.

따라서,

B

와 짝을 이룰 수 있는 자연수는 존재하지 않으며, 이는

\mathbb{N}

과

\mathcal{P}(\mathbb{N})

사이에 전단사 함수가 존재한다는 가정에 모순된다. 이 논법을 대각선 논법이라고 한다.

참조

_[1] 서적 Set Theory: With an Introduction to Real Point Sets Springer Science & Business Media
_[2] 서적 Set Theory as a Computational Logic https://www.cl.cam.a[...] University of Cambridge Computer Laboratory
_[3] 서적 Beyond the Limits of Thought Oxford University Press
_[4] 서적 Ernst Zermelo: An Approach to His Life and Work https://archive.org/[...] Springer Science & Business Media
_[5] 논문 Set theory with a universal set. Proceedings of the Tarski Symposium. Proceedings of Symposia in Pure Mathematics XXV
_[6] 간행물 Über eine elementare Frage der Mannigfaltigskeitslehre http://gdz.sub.uni-g[...]
_[7] 논문 The Empty Set, the Singleton, and the Ordered Pair https://math.bu.edu/[...] Bulletin of Symbolic Logic 2003
_[8] 서적 Conceptual Mathematics: A First Introduction to Categories https://archive.org/[...] Cambridge University Press

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com